// 埃氏筛
// https://soj.turingedu.cn/problem/50500/
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
ll rad(); // read int
const int max_size = 2 + 4e7;
const int maxn = 5 + 4e7; // maxn ^ 2 > 1e15

bool visit[maxn];
int pri[maxn], psiz;

void get_prime(int n) {
    for (int i = 2; i <= n; ++i) {
        if (visit[i]) continue;
        pri[++psiz] = i;
        if ((ll)i * i > n) continue;
        for (int j = i * i; j <= n; j += i) {
            visit[j] = true;
        }
    }
}

bool test(ll n) {
    for (int i = 1; i <= psiz && pri[i] * pri[i] <= n; ++i) {
        if (n % pri[i] == 0) return 0;
    }
    return 1;
}

int main() {
    get_prime(max_size);
    visit[1] = 1;
    int q = rad();
    rf(i, q) {
        ll tmp = rad();
        bool tag = tmp < max_size ? !visit[tmp] : test(tmp);
        printf("Case #%d: %s\n", i, tag ? "Yes" : "No");
    }
}

ll rad() {
    ll back = 0, ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}